package search;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;

import search.fifteen.PuzzleState;


/**
 * The Node is the main class for the search tree.
 * To use ordering, use the Comparator class. 
 */
public class Node {
    private final State  state;
    private final Node   parent;
    private final Action action;
    private final double cost;
    private final int    depth;

    protected Node() {
        this(null, null, null, 0);
    }
    /**
     * Create a search node with no parent node, i.e. a root node.
     * @param state the state which this node refers to, usually the initial state
     */
    public Node(State state) {
        this(state, null, null, 0);
    }
    
    /**
     * Initialise a search node.
     * @param state the state it contains
     * @param parent the parent node it derives from
     * @param action the action that we took to get here
     * @param cost the cost that has been accumulated getting here
     */
    public Node(State state, Node parent, Action action, double cost) {
        this.state=state;
        this.parent=parent;
        this.action=action;
        this.cost=cost;
        if (parent!=null)
            this.depth=parent.getDepth()+1;
        else
            this.depth=0;
    }
    
    /**
     * Expand the node into sub-nodes.
     * It uses the successor-function of the state to determine all Action/State pairs, and generates
     * a node for each.
     * @return all nodes that can be reached from this node
     */
    public Node[] expand() {
        ActionStatePair[] successors=state.successor();
        Node[] descendants=new Node[successors.length];
        for (int a=0; a<successors.length; a++) {
            Action action=successors[a].getAction();
            State child=successors[a].getState();
            descendants[a]=new Node(child, this, action, this.getCost()+state.pathcost(action));
        }
        return descendants;
    }

    /**
     * Determine all actions that were used to get to this node.
     * @return all actions that took us to this node
     */
    public Action[] getActions() {
        Action[] steps=new Action[depth];
        Node node=this;
        for (int i=0; i<depth; i++) {
            steps[i]=node.getAction();
            node=node.getParent();
        }
        return steps;
    }
    
    /**
     * @return the (last) action that took us here (from parent)
     */
    public Action getAction() {
        return action;
    }

    /**
     * @return the accumulated cost of getting here
     */
    public double getCost() {
        return cost;
    }

    /**
     * @return the tree depth of this node
     */
    public int getDepth() {
        return depth;
    }

    /**
     * @return the parent node of this node
     */
    public Node getParent() {
        return parent;
    }

    /**
     * @return the state this node contains
     */
    public State getState() {
        return state;
    }

    public static boolean areSameStates(PuzzleState s1, PuzzleState s2) {
    	for (int i = 0; i < 4; i++) {
    		for (int j = 0; j < 4; j++) {
    			if (s1.tiles[i][j] != s2.tiles[i][j]) 
    				return false;
    		}
    	}
    	return true;
    }
    /**
     * Calculate the effective branching factor for a tree search.
     * Adapted from ATILLA DEMIRAY's ANSI C CODE CALCULATING EFFECTIVE BRANCHING FACTOR
     * http://utopia.poly.edu/~ademir02/soft/sources/aisx/ebfx.htm (was available 30 Aug 2005)
     * @param nNodes number of nodes
     * @param depth depth where solution was found
     * @return the estimated effective branching factor
     */
    public static double effectiveBranchingFactor(int nNodes, int depth) {
        double maxError=0.01; // the maximum error we accept from a solution 
        double delta=0.01;    // how much we change our tested ebf each iteration   
        int signOfError=0;    // the sign of the difference between N+1 and 1+b+b^2+......+b^d
        double b=0;           // search for the optimum b will start from minimum possible b
        while (true) {        // search for b starts here
            // compute the expression 1+b+b^2+......+b^d
            double sum=1;
            for (int i=1; i<depth+1; i++) {
                sum+=Math.pow(b, (double)i);
            }
            // now the tricky bit, we compute the difference between 
            // N+1 and 1+b+b^2+......+b^d, remember that we should have N+1=1+b+b^2+......+b^d
            double error=sum-(1+(double)nNodes);
            // save previous sign of error
            int signOfPreviousError=signOfError;
            // determine the new sign of error
            if (error<0.0) // negative
                signOfError=-1;
            else // positive
                signOfError=+1;
            /* if the error calculated above is greater than the maximum acceptable error, then check if sign of error
               was changed, if so that means loop missed the root that we are looking for, then decrease b by delta and 
               decrease delta to catch root in next search if sign of error wasnt change then increase 'b' by delta
               otherwise if error is smaller than the limit return the effective branch factor */
            if (Math.abs(error)>maxError) { // error is big
                if (signOfPreviousError==signOfError || signOfPreviousError==0) {  
                    b+=delta;   // taking another step towards solution
                } else {        // change of sign which means that we jumped over the minima
                    b-=delta;   // go back
                    delta/=2;   // take smaller steps
                    signOfError=signOfPreviousError;  // undo change of sign
                }
            } else // error is small, let's return current estimate
                return(b);
        }
    }
    
    /**
     * Executes a breadth-first search from an initial state and with a queue/open list/fringe. 
     * @param initial the initial, starting state
     * @param fringe the list of all nodes that should be expanded, 
     * usually empty.
     * @return the solution node if one is found, null otherwise
     */
    //public static Node breadthFirstSearch(State initial, List<Node> fringe) {
    public static Node breadthFirstSearch(State initial, List fringe) {
        // add the initial state to the fringe
        fringe.add(new Node(initial)); 
        // loop through all nodes in the fringe
        // for testing
        //int j=0;
        while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
            // poll the first node in the list
            Node head=(Node)fringe.get(0);
            fringe.remove(0);
            // pull out the state in the node
            State state=head.getState();
            // examine it to see if it is a goal state
			//for testing
            //PuzzleState potentialChild = (PuzzleState)head.getState();
			//System.out.println(j+++"simple\n"+potentialChild.toString());
			if (state.goal()) {
                return head; // if goal state then return this node
            }
            // consider using a "closed list" for visited states (avoiding repeated states)
            
            // expand the node, and add all new states to the fringe
            fringe.addAll(Arrays.asList(head.expand())); // a list adds new nodes to the end of the queue
        }
        return null;
    }
  
    
	/**
	 * Executes a Greedy search using a heuristic 1.
	 * 
	 * @param initial
	 *            the initial, starting state
	 * @param fringe
	 *            the list of all nodes that should be expanded, usually empty.
	 * @return the solution node if one is found, null otherwise
	 * @author William & Ermin (s4098621 & s4099520)
	 */
	public static Node solveH1G(State initial, List<Node> fringe) {
		// add the initial state to the fringe
		fringe.add(new Node(initial));
		List<Node> alreadyDoneStates = new ArrayList<Node>();
		// loop through all nodes in the fringe
		while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
			// the index where the best choice node is in the fringe
			int index = 0;
			// test the heuristic against this initial value - if the tested
			// value is smaller, then it's a better state
			double heuristicCost = 2000;
			boolean isNotRepeated = true; // used to check for repeated states
			// test all the elements in the fringe BACKWARDS for the best choice
			// node
			for (int i = fringe.size() - 1; i >= 0; i--) {
				// takes out a node for testing (must be PuzzleState to access
				// the tiles)
				PuzzleState potentialChild = (PuzzleState) fringe.get(i)
						.getState();

				/* this is repeated state detection */
				for (Node n : alreadyDoneStates) {
					if (areSameStates((PuzzleState) n.getState(),
							potentialChild)) {
						isNotRepeated = false;
						break;
					}
				}
				/* end repeated state detection */

				if (isNotRepeated) { // if this state hasn't already been
					// reached, calculate its heuristic
					// value
					if (processH1(potentialChild.tiles) < heuristicCost) {
						heuristicCost = processH1(potentialChild.tiles);
						// update index if it's better then the previous one
						index = i;
					}
				}
			}
			heuristicCost = 2000; // reset for the next testing
			// extract the best choice node
			Node head = (Node) fringe.get(index);
			// place removed head from fringe into another list so we can test
			// repeated state detection
			alreadyDoneStates.add(fringe.remove(index));
			// pull out the state in the node
			State state = head.getState();
			// examine it to see if it is a goal state
			if (state.goal()) {
				// prints out the EBF value (total nodes are all in fringe +
				// previously visited states)
				System.out.println("H1G: "
						+ "Depth: "
						+ head.getDepth()
						+ " EBF: "
						+ effectiveBranchingFactor(fringe.size()
								+ alreadyDoneStates.size(), head.getDepth()));
				return head; // if goal state then return this node
			}
			// expand the node, and add all new states to the fringe
			fringe.addAll(Arrays.asList(head.expand()));
		}
		return null;
	}
    
	/**
	 * Executes a A* search using heuristic 1.
	 * 
	 * @param initial
	 *            the initial, starting state
	 * @param fringe
	 *            the list of all nodes that should be expanded, usually empty.
	 * @return the solution node if one is found, null otherwise
	 * @author William & Ermin (s4098621 & s4099520)
	 */
	public static Node solveH1A(State initial, List<Node> fringe) {
		// add the initial state to the fringe
		fringe.add(new Node(initial));
		List<Node> alreadyDoneStates = new ArrayList<Node>();
		// loop through all nodes in the fringe
		while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
			// the index where the best choice node is in the fringe
			int index = 0;
			// test the heuristic against this initial value - if the tested
			// value is smaller, then it's a better state
			double heuristicCost = 2000;
			boolean isNotRepeated = true; // used to check for repeated states
			// test all the elements in the fringe BACKWARDS for the best choice
			// node
			for (int i = fringe.size() - 1; i >= 0; i--) {
				// takes out a node for testing (must be PuzzleState to access
				// the tiles)
				PuzzleState potentialChild = (PuzzleState) fringe.get(i)
						.getState();

				/* this is repeated state detection */
				for (Node n : alreadyDoneStates) {
					if (areSameStates((PuzzleState) n.getState(),
							potentialChild)) {
						isNotRepeated = false;
						break;
					}
				}
				/* end repeated state detection */

					// reached, calculate its heuristic value
					if (processH1(potentialChild.tiles)
							+ fringe.get(i).getCost() < heuristicCost) {
						heuristicCost = processH1(potentialChild.tiles)
								+ fringe.get(i).getCost();
						// update index if it's better then the previous one
						index = i;
					}
			}
			heuristicCost = 2000;
			// extract the best choice node
			Node head = (Node) fringe.get(index);
			// place removed head from fringe into another list so we can test
			// repeated state detection
			alreadyDoneStates.add(fringe.remove(index));
			// pull out the state in the node
			State state = head.getState();
			// examine it to see if it is a goal state
			if (state.goal()) {
				// prints out the EBF value (total nodes are all in fringe +
				// previously visited states)
				System.out.println("H1A: "
						+ "Depth: "
						+ head.getDepth()
						+ " EBF: "
						+ effectiveBranchingFactor(fringe.size()
								+ alreadyDoneStates.size(), head.getDepth()));
				return head; // if goal state then return this node
			}
			// expand the node, and add all new states to the fringe
			fringe.addAll(Arrays.asList(head.expand()));
		}
		return null;
	}
    
	/**
	 * Calculates the heuristic value of the state (number of misplaced tiles).
	 * 
	 * @param tiles
	 *            the tiles of the state
	 * @return the number of misplaced tiles in the state
	 * @author William & Ermin (s4098621 & s4099520)
	 */
	private static int processH1(int[][] tiles) {

		/* basic manhatten implementation */
		int misplaced = 0;
		for (int i = 0; i < 4; i++) { // represents the horizontal
			for (int j = 0; j < 4; j++) { // represents the vertical
				if (tiles[i][j] == 1) {
					misplaced += Math.abs(i - 0) + Math.abs(j - 0);
					// test for the absolute difference between the
					// actual placement and correct placement of the tile
				}
				if (tiles[i][j] == 2) {
					misplaced += Math.abs(i - 0) + Math.abs(j - 1);
				}
				if (tiles[i][j] == 3) {
					misplaced += Math.abs(i - 0) + Math.abs(j - 2);
				}
				if (tiles[i][j] == 4) {
					misplaced += Math.abs(i - 0) + Math.abs(j - 3);
				}
				if (tiles[i][j] == 5) {
					misplaced += Math.abs(i - 1) + Math.abs(j - 0);
				}
				if (tiles[i][j] == 6) {
					misplaced += Math.abs(i - 1) + Math.abs(j - 1);
				}
				if (tiles[i][j] == 7) {
					misplaced += Math.abs(i - 1) + Math.abs(j - 2);
				}
				if (tiles[i][j] == 8) {
					misplaced += Math.abs(i - 1) + Math.abs(j - 3);
				}
				if (tiles[i][j] == 9) {
					misplaced += Math.abs(i - 2) + Math.abs(j - 0);
				}
				if (tiles[i][j] == 10) {
					misplaced += Math.abs(i - 2) + Math.abs(j - 1);
				}
				if (tiles[i][j] == 11) {
					misplaced += Math.abs(i - 2) + Math.abs(j - 2);
				}
				if (tiles[i][j] == 12) {
					misplaced += Math.abs(i - 2) + Math.abs(j - 3);
				}
				if (tiles[i][j] == 13) {
					misplaced += Math.abs(i - 3) + Math.abs(j - 0);
				}
				if (tiles[i][j] == 14) {
					misplaced += Math.abs(i - 3) + Math.abs(j - 1);
				}
				if (tiles[i][j] == 15) {
					misplaced += Math.abs(i - 3) + Math.abs(j - 2);
				}
			}
		}
		for (int j = 1; j < 4; j++) { // represents the vertical columns 
			if (tiles[0][j] == 1 && tiles[0][j - 1] == 2)
				misplaced += 2;
				// we have found a problem, so add 2 to the cost of moving that tile
			if (tiles[0][j] == 2 && tiles[0][j - 1] == 3)
				misplaced += 2;

			if (tiles[0][j] == 3 && tiles[0][j - 1] == 4)
				misplaced += 2;

			if (tiles[1][j] == 5 && tiles[0][j - 1] == 6)
				misplaced += 2;

			if (tiles[1][j] == 6 && tiles[0][j - 1] == 7)
				misplaced += 2;

			if (tiles[1][j] == 7 && tiles[0][j - 1] == 8)
				misplaced += 2;

			if (tiles[2][j] == 9 && tiles[0][j - 1] == 10)
				misplaced += 2;

			if (tiles[2][j] == 10 && tiles[0][j - 1] == 11)
				misplaced += 2;

			if (tiles[2][j] == 11 && tiles[0][j - 1] == 12)
				misplaced += 2;

			if (tiles[1][j] == 13 && tiles[0][j - 1] == 14)
				misplaced += 2;

			if (tiles[1][j] == 14 && tiles[0][j - 1] == 15)
				misplaced += 2;
		}
		return misplaced;
	}

	/**
	 * Executes a Greedy search using heuristic 2.
	 * 
	 * @param initial
	 *            the initial, starting state
	 * @param fringe
	 *            the list of all nodes that should be expanded, usually empty.
	 * @return the solution node if one is found, null otherwise
	 * @author William & Ermin (s4098621 & s4099520)
	 */
    public static Node solveH2G(State initial, List<Node> fringe) {
		// add the initial state to the fringe
		fringe.add(new Node(initial));
		List<Node> alreadyDoneStates = new ArrayList<Node>();
		// loop through all nodes in the fringe
		while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
			// the index where the best choice node is in the fringe
			int index = 0;
			// test the heuristic against this initial value - if the tested
			// value is smaller, then it's a better state
			double heuristicCost = 2000;
			boolean isNotRepeated = true; // used to check for repeated states
			// test all the elements in the fringe BACKWARDS for the best choice
			// node
			for (int i = fringe.size() - 1; i >= 0; i--) {
				// takes out a node for testing (must be PuzzleState to access
				// the tiles)
				PuzzleState potentialChild = (PuzzleState) fringe.get(i)
						.getState();

				/* this is repeated state detection */
				for (Node n : alreadyDoneStates) {
					if (areSameStates((PuzzleState) n.getState(),
							potentialChild)) {
						isNotRepeated = false;
						break;
					}
				}
				/* end repeated state detection */

				if (isNotRepeated) { // if this state hasn't already been
					// reached, calculate its heuristic
					// value
					if (processH2(potentialChild.tiles) < heuristicCost) {
						heuristicCost = processH2(potentialChild.tiles);
						// update index if it's better then the previous one
						index = i;
					}
				}
			}
			heuristicCost = 2000; // reset for the next testing
			// extract the best choice node
			Node head = (Node) fringe.get(index);
			// place removed head from fringe into another list so we can test
			// repeated state detection
			alreadyDoneStates.add(fringe.remove(index));
			// pull out the state in the node
			State state = head.getState();
			// examine it to see if it is a goal state
			if (state.goal()) {
				// prints out the EBF value (total nodes are all in fringe +
				// previously visited states)
				System.out.println("H2G: "
						+ "Depth: "
						+ head.getDepth()
						+ " EBF: "
						+ effectiveBranchingFactor(fringe.size()
								+ alreadyDoneStates.size(), head.getDepth()));
				return head; // if goal state then return this node
			}
			// expand the node, and add all new states to the fringe
			fringe.addAll(Arrays.asList(head.expand()));
		}
        return null;
    }  
    
	/**
	 * Executes a A* search using heuristic 2.
	 * 
	 * @param initial
	 *            the initial, starting state
	 * @param fringe
	 *            the list of all nodes that should be expanded, usually empty.
	 * @return the solution node if one is found, null otherwise
	 * @author William & Ermin (s4098621 & s4099520)
	 */
    public static Node solveH2A(State initial, List<Node> fringe) {
		// add the initial state to the fringe
		fringe.add(new Node(initial));
		List<Node> alreadyDoneStates = new ArrayList<Node>();
		// loop through all nodes in the fringe
		while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
			// the index where the best choice node is in the fringe
			int index = 0;
			// test the heuristic against this initial value - if the tested
			// value is smaller, then it's a better state
			double heuristicCost = 2000;
			boolean isNotRepeated = true; // used to check for repeated states
			// test all the elements in the fringe BACKWARDS for the best choice
			// node
			for (int i = fringe.size() - 1; i >= 0; i--) {
				// takes out a node for testing (must be PuzzleState to access
				// the tiles)
				PuzzleState potentialChild = (PuzzleState) fringe.get(i)
						.getState();

				/* this is repeated state detection */
				for (Node n : alreadyDoneStates) {
					if (areSameStates((PuzzleState) n.getState(),
							potentialChild)) {
						isNotRepeated = false;
						break;
					}
				}
				/* end repeated state detection */

					// reached, calculate its heuristic value
					if (processH2(potentialChild.tiles)
							+ fringe.get(i).getCost() < heuristicCost) {
						heuristicCost = processH2(potentialChild.tiles)
								+ fringe.get(i).getCost();
						// update index if it's better then the previous one
						index = i;
					}
			}
			heuristicCost = 2000;
			// extract the best choice node
			Node head = (Node) fringe.get(index);
			// place removed head from fringe into another list so we can test
			// repeated state detection
			alreadyDoneStates.add(fringe.remove(index));
			// pull out the state in the node
			State state = head.getState();
			// examine it to see if it is a goal state
			if (state.goal()) {
				// prints out the EBF value (total nodes are all in fringe +
				// previously visited states)
				System.out.println("H2A: "
						+ "Depth: "
						+ head.getDepth()
						+ " EBF: "
						+ effectiveBranchingFactor(fringe.size()
								+ alreadyDoneStates.size(), head.getDepth()));
				return head; // if goal state then return this node
			}
			// expand the node, and add all new states to the fringe
			fringe.addAll(Arrays.asList(head.expand()));
		}
		return null;
    }

    
	/**
	 * Calculates the heuristic value of the state (number of misplaced tiles).
	 * 
	 * @param tiles
	 *            the tiles of the state
	 * @return the number of misplaced tiles in the state
	 * @author William & Ermin (s4098621 & s4099520)
	 */
	private static int processH2(int[][] takenTiles) {
		// recreate the tiles, because otherwise the program accesses 
		// the values of the the actual node's tiles.
		int[][] testTiles = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 },
				{ 0, 0, 0, 0 } };
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				testTiles[i][j] = takenTiles[i][j];
			}
		}
		// initialise the variables
		int heuristicValue = 0;
		int positionRow = 9; // Stores the row of the found tile (temp value) 
		int positionColumn = 9; // stores the column of the found tile (temp value)
		int swapTile = 18; // temp variable that will contained the tile value
		while (!testGoal(testTiles)) {
			// reinitialise
			positionRow = 9;
			positionColumn = 9;
			swapTile = 18;
			boolean isFound = false;
			// first test for a state where the blank tile is actually in the correct position
			// need to now find the 1st misplaced tile, starting from the top-left.
			if (testTiles[3][3] == 0) {
				for (int i = 0; i < 4; i++) { // represents the horizontal
					for (int j = 0; j < 4; j++) { // represents the vertical
						// in these instances, the tile is correctly positioned
						if (testTiles[i][j] == 1 && i == 0 && j == 0) {
							continue;
						}
						if (testTiles[i][j] == 2 && i == 0 && j == 1) {
							continue;
						}
						if (testTiles[i][j] == 3 && i == 0 && j == 2) {
							continue;
						}
						if (testTiles[i][j] == 4 && i == 0 && j == 3) {
							continue;
						}
						if (testTiles[i][j] == 5 && i == 1 && j == 0) {
							continue;
						}
						if (testTiles[i][j] == 6 && i == 1 && j == 1) {
							continue;
						}
						if (testTiles[i][j] == 7 && i == 1 && j == 2) {
							continue;
						}
						if (testTiles[i][j] == 8 && i == 1 && j == 3) {
							continue;
						}
						if (testTiles[i][j] == 9 && i == 2 && j == 0) {
							continue;
						}
						if (testTiles[i][j] == 10 && i == 2 && j == 1) {
							continue;
						}
						if (testTiles[i][j] == 11 && i == 2 && j == 2) {
							continue;
						}
						if (testTiles[i][j] == 12 && i == 2 && j == 3) {
							continue;
						}
						if (testTiles[i][j] == 13 && i == 3 && j == 0) {
							continue;
						}
						if (testTiles[i][j] == 14 && i == 3 && j == 1) {
							continue;
						}
						if (testTiles[i][j] == 15 && i == 3 && j == 2) {
							continue;
						}
						if (testTiles[i][j] != 1) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						} else if (testTiles[i][j] != 2) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 3) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 4) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 5) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 6) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 7) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 8) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 9) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 10) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 11) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 12) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 13) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 14) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
						if (testTiles[i][j] != 15) {
							testTiles[3][3] = testTiles[i][j];
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
					}
					if (isFound) {
						break;
					}
				}
			}
			// find where the blank tile is located
			isFound = false;
			for (int i = 0; i < 4; i++) { // represents the horizontal
				for (int j = 0; j < 4; j++) { // represents the vertical
					if (testTiles[i][j] == 0 && i == 0 && j == 0) {
						testTiles[i][j] = 1;
						swapTile = testTiles[i][j];
						positionRow = i;
						isFound = true;
						positionColumn = j;
						break;
					}
					if (testTiles[i][j] == 0 && i == 0 && j == 1) {
						testTiles[i][j] = 2;
						swapTile = testTiles[i][j];
						positionRow = i;
						isFound = true;
						positionColumn = j;
						break;
					}
					if (testTiles[i][j] == 0 && i == 0 && j == 2) {
						testTiles[i][j] = 3;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 0 && j == 3) {
						testTiles[i][j] = 4;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 1 && j == 0) {
						testTiles[i][j] = 5;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 1 && j == 1) {
						testTiles[i][j] = 6;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 1 && j == 2) {
						testTiles[i][j] = 7;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 1 && j == 3) {
						testTiles[i][j] = 8;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 2 && j == 0) {
						testTiles[i][j] = 9;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 2 && j == 1) {
						testTiles[i][j] = 10;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 2 && j == 2) {
						testTiles[i][j] = 11;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 2 && j == 3) {
						testTiles[i][j] = 12;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 3 && j == 0) {
						testTiles[i][j] = 13;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 3 && j == 1) {
						testTiles[i][j] = 14;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
					if (testTiles[i][j] == 0 && i == 3 && j == 2) {
						testTiles[i][j] = 15;
						swapTile = testTiles[i][j];
						positionRow = i;
						positionColumn = j;
						isFound = true;
						break;
					}
				}
				if (isFound) {
					break;
				}
			}
			// record the place of the misplaced tile, so when we move 
			// the blank tile, it correctly positioned
			String postion = "" + positionRow + positionColumn; 
			isFound = false;
			// replace the value with the blank tile
			for (int i = 0; i < 4; i++) { // represents the horizontal
				for (int j = 0; j < 4; j++) { // represents the vertical
					String tempPosition = "" + i + j;
					if (testTiles[i][j] == swapTile) {
						if (!postion.equals(tempPosition)) {
							testTiles[i][j] = 0;
							heuristicValue++;
							isFound = true;
							break;
						}
					}
				}
				if (isFound) {
					// get out of this loop
					break;
				}
			}
		}
		return heuristicValue;
	}	
    
	/**
	 * Tests tiles to check if a goal state has been reached.
	 * 
	 * @param tiles
	 *            the tiles needed to be tested
	 * @return true is is goal state, false if not
	 * @author Taken from PuzzleState Class
	 */
	public static boolean testGoal(int[][] tiles) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (tiles[i][j] != i * 4 + j + 1) {
					if (i == 3 && j == 3)
						// found the goal state
						return true;
					return false;
				}
			}
		}
		return true;
	}
    
    
	/**
	 * Executes a Greedy search using a "number of misplaced tiles" heuristic.
	 * 
	 * @param initial
	 *            the initial, starting state
	 * @param fringe
	 *            the list of all nodes that should be expanded, usually empty.
	 * @return the solution node if one is found, null otherwise
	 * @author William & Ermin (s4098621 & s4099520)
	 */
    public static Node solveH3G(State initial, List<Node> fringe) {
		// add the initial state to the fringe
		fringe.add(new Node(initial));
		List<Node> alreadyDoneStates = new ArrayList<Node>();
		// loop through all nodes in the fringe
		while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
			// the index where the best choice node is in the fringe
			int index = 0;
			// test the heuristic against this initial value - if the tested
			// value is smaller, then it's a better state
			double heuristicCost = 2000;
			boolean isNotRepeated = true; // used to check for repeated states
			// test all the elements in the fringe BACKWARDS for the best choice
			// node
			for (int i = fringe.size() - 1; i >= 0; i--) {
				// takes out a node for testing (must be PuzzleState to access
				// the tiles)
				PuzzleState potentialChild = (PuzzleState) fringe.get(i)
						.getState();

				/* this is repeated state detection */
				for (Node n : alreadyDoneStates) {
					if (areSameStates((PuzzleState) n.getState(),
							potentialChild)) {
						isNotRepeated = false;
						break;
					}
				}
				/* end repeated state detection */

				if (isNotRepeated) { // if this state hasn't already been
					// reached, calculate its heuristic
					// value
					if (processH3(potentialChild.tiles) < heuristicCost) {
						heuristicCost = processH3(potentialChild.tiles);
						// update index if it's better then the previous one
						index = i;
					}
				}
			}
			heuristicCost = 2000; // reset for the next testing
			// extract the best choice node
			Node head = (Node) fringe.get(index);
			// place removed head from fringe into another list so we can test
			// repeated state detection
			alreadyDoneStates.add(fringe.remove(index));
			// pull out the state in the node
			State state = head.getState();
			// examine it to see if it is a goal state
			if (state.goal()) {
				// prints out the EBF value (total nodes are all in fringe +
				// previously visited states)
				System.out.println("H3G: "
						+ "Depth: "
						+ head.getDepth()
						+ " EBF: "
						+ effectiveBranchingFactor(fringe.size()
								+ alreadyDoneStates.size(), head.getDepth()));
				return head; // if goal state then return this node
			}
			// expand the node, and add all new states to the fringe
			fringe.addAll(Arrays.asList(head.expand()));
		}
        return null;
    }  
    
	/**
	 * Executes a A* search using a "number of misplaced tiles" heuristic.
	 * 
	 * @param initial
	 *            the initial, starting state
	 * @param fringe
	 *            the list of all nodes that should be expanded, usually empty.
	 * @return the solution node if one is found, null otherwise
	 * @author William & Ermin (s4098621 & s4099520)
	 */
    public static Node solveH3A(State initial, List<Node> fringe) {
		// add the initial state to the fringe
		fringe.add(new Node(initial));
		List<Node> alreadyDoneStates = new ArrayList<Node>();
		// loop through all nodes in the fringe
		while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
			// the index where the best choice node is in the fringe
			int index = 0;
			// test the heuristic against this initial value - if the tested
			// value is smaller, then it's a better state
			double heuristicCost = 2000;
			boolean isNotRepeated = true; // used to check for repeated states
			// test all the elements in the fringe BACKWARDS for the best choice
			// node
			for (int i = fringe.size() - 1; i >= 0; i--) {
				// takes out a node for testing (must be PuzzleState to access
				// the tiles)
				PuzzleState potentialChild = (PuzzleState) fringe.get(i)
						.getState();

				/* this is repeated state detection */
				for (Node n : alreadyDoneStates) {
					if (areSameStates((PuzzleState) n.getState(),
							potentialChild)) {
						isNotRepeated = false;
						break;
					}
				}
				/* end repeated state detection */

					// reached, calculate its heuristic value
					if (processH3(potentialChild.tiles)
							+ fringe.get(i).getCost() < heuristicCost) {
						heuristicCost = processH3(potentialChild.tiles)
								+ fringe.get(i).getCost();
						// update index if it's better then the previous one
						index = i;
					}
			}
			heuristicCost = 2000;
			// extract the best choice node
			Node head = (Node) fringe.get(index);
			// place removed head from fringe into another list so we can test
			// repeated state detection
			alreadyDoneStates.add(fringe.remove(index));
			// pull out the state in the node
			State state = head.getState();
			// examine it to see if it is a goal state
			if (state.goal()) {
				// prints out the EBF value (total nodes are all in fringe +
				// previously visited states)
				System.out.println("H3A: "
						+ "Depth: "
						+ head.getDepth()
						+ " EBF: "
						+ effectiveBranchingFactor(fringe.size()
								+ alreadyDoneStates.size(), head.getDepth()));
				return head; // if goal state then return this node
			}
			// expand the node, and add all new states to the fringe
			fringe.addAll(Arrays.asList(head.expand()));
		}
		return null;
    }
    
	/**
	 * Calculates the heuristic value of the state (number of misplaced tiles).
	 * 
	 * @param tiles
	 *            the tiles of the state
	 * @return the number of misplaced tiles in the state
	 * @author William & Ermin (s4098621 & s4099520)
	 */
	private static int processH3(int[][] tiles) {
		int misplaced = 0;
		if (tiles[0][0] != 1) {
			misplaced++;
		}
		if (tiles[0][1] != 2) {
			misplaced++;
		}
		if (tiles[0][2] != 3) {
			misplaced++;
		}
		if (tiles[0][3] != 4) {
			misplaced++;
		}
		if (tiles[1][0] != 5) {
			misplaced++;
		}
		if (tiles[1][1] != 6) {
			misplaced++;
		}
		if (tiles[1][2] != 7) {
			misplaced++;
		}
		if (tiles[1][3] != 8) {
			misplaced++;
		}
		if (tiles[2][0] != 9) {
			misplaced++;
		}
		if (tiles[2][1] != 10) {
			misplaced++;
		}
		if (tiles[2][2] != 11) {
			misplaced++;
		}
		if (tiles[2][3] != 12) {
			misplaced++;
		}
		if (tiles[3][0] != 13) {
			misplaced++;
		}
		if (tiles[3][1] != 14) {
			misplaced++;
		}
		if (tiles[3][2] != 15) {
			misplaced++;
		}
		return misplaced;
	}

	/**
	 * Executes a Greedy search using the manhatten distance heuristic.
	 * 
	 * @param initial
	 *            the initial, starting state
	 * @param fringe
	 *            the list of all nodes that should be expanded, usually empty.
	 * @return the solution node if one is found, null otherwise
	 * @author William & Ermin (s4098621 & s4099520)
	 */
    public static Node solveH4G(State initial, List<Node> fringe) {
		// add the initial state to the fringe
		fringe.add(new Node(initial));
		List<Node> alreadyDoneStates = new ArrayList<Node>();
		// loop through all nodes in the fringe
		while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
			// the index where the best choice node is in the fringe
			int index = 0;
			// test the heuristic against this initial value - if the tested
			// value is smaller, then it's a better state
			double heuristicCost = 2000;
			boolean isNotRepeated = true; // used to check for repeated states
			// test all the elements in the fringe BACKWARDS for the best choice
			// node
			for (int i = fringe.size() - 1; i >= 0; i--) {
				// takes out a node for testing (must be PuzzleState to access
				// the tiles)
				PuzzleState potentialChild = (PuzzleState) fringe.get(i)
						.getState();

				/* this is repeated state detection */
				for (Node n : alreadyDoneStates) {
					if (areSameStates((PuzzleState) n.getState(),
							potentialChild)) {
						isNotRepeated = false;
						break;
					}
				}
				/* end repeated state detection */

				if (isNotRepeated) { // if this state hasn't already been
					// reached, calculate its heuristic
					// value
					if (processH4(potentialChild.tiles) < heuristicCost) {
						heuristicCost = processH4(potentialChild.tiles);
						// update index if it's better then the previous one
						index = i;
					}
				}
			}
			heuristicCost = 2000; // reset for the next testing
			// extract the best choice node
			Node head = (Node) fringe.get(index);
			// place removed head from fringe into another list so we can test
			// repeated state detection
			alreadyDoneStates.add(fringe.remove(index));
			// pull out the state in the node
			State state = head.getState();
			// examine it to see if it is a goal state
			if (state.goal()) {
				// prints out the EBF value (total nodes are all in fringe +
				// previously visited states)
				System.out.println("H4G: "
						+ "Depth: "
						+ head.getDepth()
						+ " EBF: "
						+ effectiveBranchingFactor(fringe.size()
								+ alreadyDoneStates.size(), head.getDepth()));
				return head; // if goal state then return this node
			}
			// expand the node, and add all new states to the fringe
			fringe.addAll(Arrays.asList(head.expand()));
		}
        return null;
    }  
    
	/**
	 * Executes a A* search using the manhatten distance heuristic.
	 * 
	 * @param initial
	 *            the initial, starting state
	 * @param fringe
	 *            the list of all nodes that should be expanded, usually empty.
	 * @return the solution node if one is found, null otherwise
	 * @author William & Ermin (s4098621 & s4099520)
	 */
    public static Node solveH4A(State initial, List<Node> fringe) {
		// add the initial state to the fringe
		fringe.add(new Node(initial));
		List<Node> alreadyDoneStates = new ArrayList<Node>();
		// loop through all nodes in the fringe
		while (!fringe.isEmpty()) { // test if fringe is empty, if yes "failure"
			// the index where the best choice node is in the fringe
			int index = 0;
			// test the heuristic against this initial value - if the tested
			// value is smaller, then it's a better state
			double heuristicCost = 2000;
			boolean isNotRepeated = true; // used to check for repeated states
			// test all the elements in the fringe BACKWARDS for the best choice
			// node
			for (int i = fringe.size() - 1; i >= 0; i--) {
				// takes out a node for testing (must be PuzzleState to access
				// the tiles)
				PuzzleState potentialChild = (PuzzleState) fringe.get(i)
						.getState();

				/* this is repeated state detection */
				for (Node n : alreadyDoneStates) {
					if (areSameStates((PuzzleState) n.getState(),
							potentialChild)) {
						isNotRepeated = false;
						break;
					}
				}
				/* end repeated state detection */

					// reached, calculate its heuristic value
					if (processH4(potentialChild.tiles)
							+ fringe.get(i).getCost() < heuristicCost) {
						heuristicCost = processH4(potentialChild.tiles)
								+ fringe.get(i).getCost();
						// update index if it's better then the previous one
						index = i;
					}
			}
			heuristicCost = 2000;
			// extract the best choice node
			Node head = (Node) fringe.get(index);
			// place removed head from fringe into another list so we can test
			// repeated state detection
			alreadyDoneStates.add(fringe.remove(index));
			// pull out the state in the node
			State state = head.getState();
			// examine it to see if it is a goal state
			if (state.goal()) {
				// prints out the EBF value (total nodes are all in fringe +
				// previously visited states)
				System.out.println("H4A: "
						+ "Depth: "
						+ head.getDepth()
						+ " EBF: "
						+ effectiveBranchingFactor(fringe.size()
								+ alreadyDoneStates.size(), head.getDepth()));
				return head; // if goal state then return this node
			}
			// expand the node, and add all new states to the fringe
			fringe.addAll(Arrays.asList(head.expand()));
		}
		return null;
    }
    
	/**
	 * Calculates the heuristic value of the state (manhatten distance).
	 * 
	 * @param tiles
	 *            the tiles of the state
	 * @return the number of misplaced tiles in the state
	 * @author William & Ermin (s4098621 & s4099520)
	 */
    private static int processH4(int[][] tiles){
        int heuristicValue = 0;
        for (int i = 0; i < 4; i++) { // represents the horizontal
        	for (int j = 0; j < 4; j++) { // represents the vertical
                if (tiles[i][j] == 1) {
                	// add the absolute distance away from the actual
                	// place the tile should be
                	heuristicValue += Math.abs(i-0) + Math.abs(j-0);
                }
                if (tiles[i][j] == 2) {
                	heuristicValue += Math.abs(i-0) + Math.abs(j-1);
                }
                if (tiles[i][j] == 3) {
                	heuristicValue += Math.abs(i-0) + Math.abs(j-2);
                }
                if (tiles[i][j] == 4) {
                	heuristicValue += Math.abs(i-0) + Math.abs(j-3);
                }
                if (tiles[i][j] == 5) {
                	heuristicValue += Math.abs(i-1) + Math.abs(j-0);
                }
                if (tiles[i][j] == 6) {
                	heuristicValue += Math.abs(i-1) + Math.abs(j-1);
                }
                if (tiles[i][j] == 7) {
                	heuristicValue += Math.abs(i-1) + Math.abs(j-2);
                }
                if (tiles[i][j] == 8) {
                	heuristicValue += Math.abs(i-1) + Math.abs(j-3);
                }
                if (tiles[i][j] == 9) {
                	heuristicValue += Math.abs(i-2) + Math.abs(j-0);
                }
                if (tiles[i][j] == 10) {
                	heuristicValue += Math.abs(i-2) + Math.abs(j-1);
                }
                if (tiles[i][j] == 11) {
                	heuristicValue += Math.abs(i-2) + Math.abs(j-2);
                }
                if (tiles[i][j] == 12) {
                	heuristicValue += Math.abs(i-2) + Math.abs(j-3);
                }
                if (tiles[i][j] == 13) {
                	heuristicValue += Math.abs(i-3) + Math.abs(j-0);
                }
                if (tiles[i][j] == 14) {
                	heuristicValue += Math.abs(i-3) + Math.abs(j-1);
                }
                if (tiles[i][j] == 15) {
                	heuristicValue += Math.abs(i-3) + Math.abs(j-2);
                }

        	}
        }
    	return heuristicValue;
    }
}
